591，二叉树的垂序遍历
问题描述
来源：LeetCode第987题
难度：困难
给你二叉树的根结点root，请你设计算法计算二叉树的垂序遍历序列。对位于(row,col)的每个结点而言，其左右子结点分别位于(row+1,col-1)和(row+1,col+1)。树的根结点位于(0,0)。
二叉树的垂序遍历从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。
返回二叉树的垂序遍历序列。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点9在此列中。
列 0 ：只有结点3和15在此列中，按从上到下顺序。
列 1 ：只有结点20在此列中。
列 2 ：只有结点7在此列中。
示例 2：
输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点4在此列中。
列 -1 ：只有结点2在此列中。
列 0 ：结点1、5和6都在此列中。
1在上面，所以它出现在前面。
5和6位置都是(2,0)，所以按值从小到大排序，5在6的前面。
列 1 ：只有结点3在此列中。
列 2 ：只有结点7在此列中。
示例 3：
输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例2完全相同，只是结点5和6在树中的位置发生了交换。
因为5和6的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。
提示：
树中结点数目总数在范围[1,1000]内
0 <= Node.val <= 1000
问题分析
这题虽然是hard，但其实没有什么难度，做这题我最先想到的就是BFS遍历，如果当前节点是第m列，那么他的左子节点就是第m-1列，右子节点就是m+1列
所以我们可以从上到下一层一层的遍历，使用一个map来存储，map的key存储的是第几列，value是那个列的集合。辛辛苦苦写完之后发现运行不通过（代码放在了下面，有兴趣的可以看下），这是因为题中有这样一句话，如果同行同列上有多个结点，则按结点的值从小到大进行排序。也就是说如果两个节点位置重合了还要按照大小进行排序。
所以这题我们只能按照常规方式来解决，就是先记录下每个节点的值和坐标，最后再把他们按照同一列的顺序放到集合中，关于二叉树的遍历有多种，我们之前也介绍过一些
来看下代码
public List<List<Integer>> verticalTraversal(TreeNode root) {
//list集合中的元素是一个数组，每个数组的长度都是3，第1个值表示
//节点的值，第2个和第3个值表示节点的横坐标和竖坐标
List<int[]> mList = new ArrayList<>();
//计算所有节点的值和坐标，根节点的坐标是（0，0）
dfs(root, 0, 0, mList);
//排序，排序的原则是先排左边一列，所以首先比较的是数组的第3个值（
//纵坐标），然后每一列从上到下也就是数组的第2个值（横坐标），如果
//前面两个值是一样的说明他们的坐标重合了，要按值从大到小排序
Collections.sort(mList, (arr1, arr2) -> {
//先按照纵坐标排序
if (arr1[2] != arr2[2])
return arr1[2] - arr2[2];
if (arr1[1] != arr2[1])
return arr1[1] - arr2[1];
//如果坐标一样，再按照值排序
return arr1[0] - arr2[0];
});
//把节点的值进行垂序分类
List<List<Integer>> res = new ArrayList<>();
res.add(new ArrayList<>());
//因为上面排序了，所以这里首先遍历的就是最左边一列的值,
//然后是第二列……
for (int i = 0; i < mList.size(); i++) {
//取出数组（包含当前节点的值和坐标）
int[] arr = mList.get(i);
//当前节点的值
int value = arr[0];
//如果当前节点和前一个节点不在同一列，说明到下一
//列了，需要初始化下一列的集合
if (i > 0 && arr[2] != mList.get(i - 1)[2])
res.add(new ArrayList<>());
//把当前节点的值添加到当前列中
res.get(res.size() - 1).add(value);
}
return res;
}
private void dfs(TreeNode node, int i, int j, List<int[]> mList) {
if (node == null)
return;
//把当前节点的值和坐标加入到集合中,当前节点的坐标是（i，j）
mList.add(new int[]{node.val, i, j});
//遍历左子节点
dfs(node.left, i + 1, j - 1, mList);
//遍历右子节点
dfs(node.right, i + 1, j + 1, mList);
}
//错误的代码（同一行和同一列的两个值没有按照大小进行排序）
public List<List<Integer>> verticalTraversal(TreeNode root) {
Map<Integer, ArrayList<Integer>> map = new HashMap<>();
//存放节点的值
Queue<TreeNode> nodeQueue = new LinkedList<>();
//存放每个节点对应第几列
Queue<Integer> lineQueue = new LinkedList<>();
//根节点是第0列，他左子节点的列是负数，右子节点的列是正数
nodeQueue.add(root);
lineQueue.add(0);
//记录最小的列，也就是最左边的列
int mineLine = 0;
while (!nodeQueue.isEmpty()) {
//当前节点及对应的列出队
TreeNode curNode = nodeQueue.poll();
int line = lineQueue.poll();
//记录最左边的列
mineLine = Math.min(mineLine, line);
//如果对应列的集合不存在就初始化一个
if (!map.containsKey(line)) {
map.put(line, new ArrayList<>());
}
//把当前节点对应的值加入到当前节点对应列的集合中
map.get(line).add(curNode.val);
//左子节点不为空，就把他以及他所在的列加入到队列中
if (curNode.left != null) {
nodeQueue.add(curNode.left);
lineQueue.add(line - 1);
}
//右子节点同上
if (curNode.right != null) {
nodeQueue.add(curNode.right);
lineQueue.add(line + 1);
}
}
//把Map转化为List，map中key存储的是第几列，
//value存储的是每一列的集合
List<List<Integer>> res = new ArrayList<>();
int end = mineLine + map.size();
for (int i = mineLine; i < end; i++) {
res.add(map.get(i));
}
return res;
}
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。